FenwickTree and Counting Inversions

Not very clever to forget all these.

---

FenwickTree 树状数组

CHN reference from zhihu

Common data structure in programming contest to answer range query questions. Simple implementation and less functionalities, $O(n)$extra space, query and edit in $O(logn)$.

Idea: represent every index in binary and save sum of all “smaller” index values, where “smaller” is defined by position of last non-zero bit (001 < 010 < 100, 011< 100).

That is, tree[(100)]=a[(001)]+a[(010)]+a[(011)]+a[(100)] . And we have tree[(010)]=a[(001)]+a[(010)],tree[(011)]=a[(011)], so that we can represent “larger” index with “smaller” one: tree[(100)]=tree[(010)]+tree[(011)]+a[(100)] by finding the next “smaller” index (caculate by i & (-i)).

NOTE: to avoid endless loop, we leave tree[0] zero and start the structure from tree[1].

void update(int pos, int v){
	for(int i=pos;i<=n;i=(i&(-i)))
    tree[i]+=v;
}

int sum(int pos){
  int res=0;
  for(int i=pos;i<=n;i=(i&(-i)))
    res+=tree[i];
  return res;
}

int query(int l, int r){
  return sum(r)-sum(l-1);
}

Counting Inversions Online

Update fenwick tree with update(a[i],1) when the current number is a[i]. This means we mark a[i] as already presented and we can later count matching inversions use query(a[i],n) (every number larger than a[i] forms an inversion, so we use fenwick tree to count sum).

Exercise: AtCoder ABC 190 F

每次移动，变化的inverison数量都是规律的，只需要算一次

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,a,n) for(int i=a;i<n;i++)
#define per(i,a,n) for(int i=n-1;i>=a;i--) 
const int N = 3e5+10;

int n;
int fen[N];

void update(int i, int v){
    for(int j=i;j<=n;j+=(j&(-j))){
        fen[j]+=v;
    }
}

int sum(int i){
    int res=0;
    for(int j=i;j>0;j-=(j&(-j))){
        res+=fen[j];
    }
    return res;
}

int query(int l, int r){
    return sum(r)-sum(l-1);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin>>n;

    int a[N];
    rep(i,0,n){
        cin>>a[i];
        a[i]+=1;
    }

    ll res=0;
    rep(i,0,n){
        res+=query(a[i],n);
        update(a[i],1);
    }
    
    cout<<res<<endl;
    rep(k,0,n-1){
        res-=a[k]-1;
        res+=n-1-(a[k]-1);
        cout<<res<<endl;
    }

    return 0;
}